COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.<<	TWO COLUMN FORMAT	by L. Earnest		February 1975
C00004 00003	.device xgp
C00006 00004	.<< cover >>
C00008 00005	.if xcribl then start twocol end
C00020 00006	.skip 2
C00021 00007	.skip 200
C00028 00008	1. Johan de Kleer, Jon Doyle, Guy L. Steele Jr. and Gerald Jay Sussman,
C00035 00009	.head←77		<< monthly cost of computer account for one person >>
C00037 00010	.gtot←0
C00039 00011	.begin "groups" fill crbreak preface 0 nojust indent 0,6
C00042 ENDMK
C⊗;
.<<	TWO COLUMN FORMAT	by L. Earnest		February 1975
.		
.			Sections
.Begin each segment with the appropriate one of the following macros
.S <section name>
.SS <subsection name>
.SSS <subsubsection name>
.APP <appendix name>
.If the name is more than one line long, enclose it in vertical bars ("|").
.
.If you wish to use a subtitle in the text but you do not want it to
.appear in the Table of Contents, you can use the following macro to
.make it centered in boldface:
. CB <subtitle>
.
.A list of people on the project should appear just under the project title,
.preceded by "//pers".  This will cause the word "Personnel: " to be printed
.followed by the list of people, with special indentation.
.
.There are some other macros whose use you can probably deduce from context
.or from their definitions below.
.>>
.device xgp;
.turn on "α%";
.font 1 "nonm"; font 2 "nonmi"; font 3 "nonmb";
.font 4 "ngr40"; FONT 5 "nonh"; font 6 "ngr30"; font 7 "bdr40";

.sides←1;
.require "twocol.pub[sub,sys]" source_file;

.MACRO YON(LBL)  ⊂ "Section "; SUB2! LBL ⊃;

.<< leave space for a full page figure >>
.MACRO FIG(NAME) ⊂ SKIP TO COLUMN 1
.GROUP SKIP 20
NAME
.next page; ⊃

.MACRO BC ⊂ BEGIN PREFACE 0; INDENT 1,4; CRBREAK nojust ⊃

.MACRO BS ⊂ BEGIN PREFACE 0; INDENT 1,4; nojust ⊃

.MACRO SUB(IND) ⊂ INDENT 0,IND; TABS IND+1;⊃

.MACRO IB ⊂ turn on "%";
.AT """" ⊂ (IF THISFONT=1 THEN "%3" ELSE "%1"); ⊃
.AT "<" ⊂ "%2" ⊃;  AT ">" ⊂ "%1" ⊃;
. ⊃

.MACRO BIB  ⊂  CB(References);
.	BEGIN INDENT 0,3; NOJUST; IB;
.	AT "AIM-" ⊂ "Stanford AI Memo AαIαMα-" ⊃;
.	COUNT exref TO 200
.	AT "⊗" ⊂ IF LINES<3 THEN NEXT COLUMN; NEXT EXREF; ("["&EXREF&"]  ") ⊃
.	⊃
.at "//pers";	⊂ once nojust; indent 0,5; ("%3Personnel: %1"); ⊃;
.
.MACRO GET(FILE) ⊂ BEGIN "FILE"
.REQUIRE "FILE" SOURCE;
.END "FILE"
. ⊃

.at "//pers";	⊂ once fill nojust; indent 0,5; ib; turn on "#";
.  at "sra"	⊂ "%2Student Research Assistants:%1"	⊃
.  ("%3Personnel: %1");
.  ⊃;
.SECNAME←"";
.portion some; place text;
.<< cover >>
.onecol;
.macro titles(smal,larg);	⊂
.CENTER SELECT smal

Supplementary Proposal to
.SKIP 2; select larg
Defense
Advanced Research Projects Agency
.SKIP 2; select smal
for research in
.SKIP 2; select larg;
Computer Science
.select smal

John McCarthy, Professor of Computer Science
Principal Investigator

.skip 2;
.⊃

.titles(4,5); skip 3;
.skip 3;
June 1980
.SKIP; select 7;
Computer Science Department
.select 5;
Stanford University
.count page
.if xcribl then start twocol end;
.s "Modelling Deliberation, Action and Introspection"
.nojust
	This is a proposal to extend the work of the Formal
Reasoning Group of the Stanford Artificial Intelligence Laboratory
to study programs modelling deliberation, action and introspection.
The work will be done by Jon Doyle and by John McCarthy.
Doyle's work requires additional DARPA support amounting to $62,055
for the period October 1, 1980 thru October 31, 1981
as described in the budgetary section of this proposal.
No additional support is requested for McCarthy.

	Advanced intelligent computer programs must reason about
the effects of their potential future actions, and this includes
reasoning about their own ability to solve problems by reason and
action.
For example, a person familiar with air travel knows that when
he reaches an intermediate airport, he will be able to determine
the gate and time of his outgoing airplane, and he knows that
he doesn't need this information in advance.  However, a
non English speaking person needs to plan how he is going to
learn this information - by getting someone to write appropriate
names and requests on a card or by finding an interpreter.
A person unfamiliar with air travel
may not even know what he has to learn, but he probably does
know that the air travel system will take care of him if he
has no unusual problems.  More generally, whenever an executive
decides that getting a job done right requires his own presence
at the scene of action, he is anticipating problems that require
his own special knowledge, priorities for different goals,
ability and authority.

	A promising approach is to regard reasoning itself as
a species of action that whose effects can be reasoned about.
Thus the program must reason about what it would
be able to do or would do in hypothetical future circumstances.
Carrying this out accurately and effectively involves self-observation
akin to human introspection.
Self-observation includes making and examining traces of inferences
made so that when a conclusion has to be revised, the reasoning
that led to it can be identified and the assumption or conjectural
conclusion that has to be taken back can be located.

	Much human decision making involves processes that may be
called %2dialectical argumentation%1.  Reasons for and against
a contemplated course of action are developed and played against
one another.  This process, which we believe is also required for
advanced computer intelligence, is quite different from the mathematical
deductions heretofore carried out by computer programs.

	In particular,
it involves non-monotonic reasoning of the kinds recently studied
by McCarthy (1980), McDermott and Doyle (1980), Doyle (1979) and Reiter
(1980).  The identification of non-monotonic reasoning as a process
 distinct from logical deduction but just as formal was accomplished
in various formalisms in the above cited papers.  It represents
a major discovery by workers in AI.  Logicians and philosophers
have from time to time
asserted the existence of non-deductive modes of reasoning but have
generally supposed them to be non-formalizable.  Now that AI has
established an entry into this field, logicians and philosophers
are also beginning to work on it.

	Consider what happens when a person proposes
an argument and then thinks of a counter-argument.  The original
argument leads to a certain conclusion.  If this conclusion were
a logical consequence, in the sense of mathematical logic, then
no additional considerations would change the conclusion unless
some of the premises were found to be incorrect.  Actually such
arguments are almost never logical deductions but non-monotonic
consequences of two kinds.

	One kind of non-monotonic conclusion is the default.  A default
is represented by a sentence that is taken to be true provided
other sentences being considered don't refute it.  An example from
Doyle (1979) is %2"The meeting is on Wednesday unless there is
a reason why not"%1.  A program will use this default to conclude
that the meeting is on Wednesday unless it has a sentence asserting
something incompatible like a conflicting meeting on Wednesday.

	Another kind of non-monotonic consequence occurs when the
facts at a person's or program's disposal show the existence of
certain objects of a given kind, and the person or program
concludes that these are all of the objects of the given kind.
Thus  we may know that a boat has a leak and lacks oars, and we
may conjecture (non-monotonically) that these are the only "things"
wrong with the boat.

	Argument, whether with another person or with oneself, often
involves finding reasons permitting such non-monotonically obtained
conclusions and then finding counter arguments.  In the above
examples, a counter argument might involve a non-monotonic deduction
that there is another group in Wednesday's meeting room or that
the boat also has a broken rudder.  Counter-counter arguments may
involve asserting the existence of another room or a plan for
fixing the rudder.

	We propose to extend the work of our Formal Reasoning Group
to develop theories and write programs that will decide what to
do by reasoning that includes introspection and dialectical argumentation.

.cb Earlier Work

	The proposed work will be based on ideas in Jon Doyle's (1980) PhD
dissertation and on approaches to non-monotonic reasoning by
Doyle (1979) and by McCarthy (1980).

	Doyle's thesis investigates the problem of controlling or
directing the reasoning and actions of a computer program.  The basic
approach explored is to view reasoning as a species of action, so that a
program might apply its reasoning powers to the task of deciding what
inferences to make as well as deciding what other actions to take.  Doyle
proposed a design for the architecture of reasoning programs.  This
architecture involves several of the features mentioned earlier, including
self-consciousness, intentional actions, deliberate
adaptations, and a form of decision-making based on dialectical
argumentation.  

	A program based on this architecture would inspect itself,
describe aspects of itself to itself, and use this self-reference and
these self-descriptions in making decisons and taking actions.  The
program's mental life would include awareness of its own concepts, beliefs,
desires, intentions, inferences, actions, and skills.  All of these are
represented by self-descriptions in a single sort of language, so that the
program has access to all of these aspects of itself, and can reason about
them in the same terms.

.cb Objectives

	During the thirteen month period of this addition to
work, the studies will mainly be conceptual.  This is
partly because these ideas require additional theoretical work
before they can be embodied in programs and partly because
programs that keep a trace of their own reasoning processes
may require bigger memories than are currently available for
single processes at Stanford.  In any case, implementation
will be a large enough project to require very careful planning.

	By the end of 1981, we will have planned a system that
will be able to reason about its own actions and "thoughts" and
carry out internal arguments as well as simpler forms of non-monotonic
reasoning.
.skip 2
.cb References

%3Doyle, J. (1979): "A truth maintainance system",
%2Artificial Intelligence 12%1, 231-272

%3Doyle, J. (1980): "A model for deliberation, action, and introspection"
%2PhD Thesis, MIT AI Laboratory TR-581%1

%3McCarthy, J. (1980): "Circumscription -  a form of non-monotonic reasoning"
%2Stanford Artificial Intelligence Laboratory Memo AIM-334%1

%3McDermott, Drew and Jon Doyle (1980): "Non-monotonic logic I",
%2Artificial Intelligence%1, to appear

%3Reiter, Raymond (1980)%1: "A logic for default reasoning",
%2Artificial Intelligence%1, to appear

.skip 200;
.begin center select 3
CURRICULUM VITAE
of
Jon Doyle
.end
.skip 2;
.begin "oner"
.fill nojust crbreak; indent 0,8; preface 0;
%1Upcoming Position:
	Research Associate
	Artificial Intelligence Laboratory
	Stanford University
.skip
Present Position:
	Scientist
	Artificial Intelligence Laboratory
	Massachusetts Institute of Technology
.skip
Address:
	305 Memorial Drive, #612-A
	Cambridge, Massachusetts 02139
.skip
Telephone: (617) 494-9214
.skip
Citizenship: United States of America
.skip
Principal Fields of Professional Interest:
	Intelligence
	Theory of Computation
	Philosophy
	Logic
	Mathematics
	Physics
.end "oner";
Education:
.begin fill nojust; preface 1;indent 0,2;crspace
1971-72	  South Texas Junior College, Houston, Texas.

1972-74   University of Houston, B.S. in Mathematics, December 1974.
Senior Honors Thesis under Prof. J. A. Schatz on "Computational
Investigations of Non-Repetitive Sequences."

1975-77   M.I.T., S.M. in Electrical Engineering and Computer Science, June 1977.
Thesis under Prof. G. J. Sussman on "Truth Maintenance Systems for Problem Solving."

1977-80   M.I.T., Ph.D. in Artificial Intelligence, June 1980.
Thesis under Prof. G. J. Sussman on "A Model for Deliberation,
Action, and Introspection."  Profs. M. Minsky, P. Szolovits, and
D. McDermott (Yale), readers.

History of Employment:

May 1974 - August 1974  Symbiotics International, Inc., Houston, Texas
Development and maintenance of business accounting programs.

January 1975 - July 1975  Shell Oil Company, Houston, Texas
Development of a user environment for geophysical processing in the Technical Computing
Division.
.end
.skip;
.begin "one"
.fill nojust crbreak; indent 0,8; preface 0;
Awards Received:
	1975-1980 Fannie and John Hertz Foundation Graduate Fellowship
	1975 NSF Honorable Mention
	1974 Summa Cum Laude, University of Houston
	1974 Honors in Mathematics, University of Houston
	1974 Honors Program, University of Houston
	1974 First prize Mathematics Contest, University of Houston
	1973 Third prize Mathematics Contest, University of Houston
	1973 Outstanding First-year Student of Russian, University of Houston
.skip;
Current Organization Memberships:
	American Association for the Advancement of Science
	American Mathematical Society
	Association for Computing Machinery
	Boston Museum of Fine Arts
	Mathematical Association of America
	MIT Musical Theater Guild
	Sigma Xi
.skip;
Sigart, Pi Mu Epsilon, Phi Kappa Phi, Omega Delta Kappa
.skip;
Past Organization Memberships:
	MIT Choral Society (1979)
	MIT Symphony Orchestra (1977-78)
.skip;
Offices:
	Director of Univ. of Houston chapter of Pi Mu Epsilon (1974)
	MIT Ashdown House Executive Committee (1978-79)
	Associate Editor of ACM SIGART Newsletter (1978-79)
.end "one"

%3Publications:%1

Papers in Refereed Journals:
.begin "multi"
.fill nojust indent 0,2; preface 1;
1. Jon Doyle and Ronald L. Rivest,
"Linear Expected Time of a Simple Union-Find Algorithm",
%2Information Processing Letters%1, Volume 5, Number 5, (November 1976), pp. 146-148.

2. Jon Doyle,
"A Truth Maintenance System"
%2Artificial Intelligence 12%1 (1979), 231-272.
 Also MIT AI Lab Memo 521, June 1979.

3. Drew McDermott and Jon Doyle,
"Non-Monotonic Logic I",
to appear in %2Artificial Intelligence%1, 1980.
Also MIT AI Lab Memo 468, August 1978.
Abstract in %2Notices of the AMS%1, V. 26, No. 1 (Jan. 1979), #79T-E4, p. A-16.

Papers in Other Journals

1. Jon Doyle and Philip London,
 "A Selected Descriptor-Indexed Bibliography to the Literature on Belief Revision",
 %2ACM SIGART Newsletter%1, No. 71, 7-23, 1980.
 Also MIT AI Lab Memo 568, February 1980.

2. Jon Doyle
 "Historical Annotations and Humble Databases",
 to appear in %2ACM SIGMOD Record%1.

Proceedings of Refereed Conferences:

1. Johan de Kleer, Jon Doyle, Guy L. Steele Jr. and Gerald Jay Sussman,
 "AMORD: Explicit Control of Reasoning",
 %2Proc. ACM Conference on AI and Programming Languages%1, Rochester, New York, August 1977.
 Also MIT AI Lab Memo 427 ("Explicit Control of Reasoning"), June 1977.

2. Jon Doyle,
 "Truth Maintenance Systems for Problem Solving",
 %2Proc. Fifth International Joint Conference on Artificial Intelligence%1, Cambridge,
Massachusetts, August 1977.
 Also MIT AI Lab TR-419, January 1978.

3. Jon Doyle,
"A Glimpse of Truth Maintenance",
 %2Proc. Fourth Workshop on Automated Deduction%1, Austin, Texas, February 1979.
 Also %2Proc. Sixth International Joint Conference on Artificial Intelligence%1, Tokyo,
Japan, August 1979.
 Also MIT AI Lab Memo 461, February 1978.

4. Drew McDermott and Jon Doyle,
 "Non-Monotonic Logic I (extended abstract)",
 %2Proc. Fourth Workshop on Automated Deduction%1, Austin, Texas, February 1979.

5. Drew McDermott and Jon Doyle,
 "An Introduction to Non-Monotonic Logic",
 %2Proc. Sixth International Joint Conference on Artificial Intelligence%1, Tokyo, Japan,
August 1979.

Unrefereed Conferences:

1. Jon Doyle,
 "Non-Repetitive Binary Sequences",
 727th Meeting of the American Mathematical Society, Cambridge, Massachusetts, October, 1975.
 Abstract in %2Notices of the AMS%1, Oct. 1975, p. A-660, #727-A5.
 Referee recommended but scooped for %2J. Combinatorial Theory A%1.  My theorems 1 and 2
paraphrase theorems 1 and 2 of F. M. Dekking, "On Repetitions of Blocks in Binary
Sequences," %2J. C. T. A 20%1 #3 (May 1976) 292-299.

Articles in Books:

1. Johan de Kleer, Jon Doyle, Guy L. Steele Jr. and Gerald Jay Sussman,
 "Explicit Control of Reasoning",
 %2Artificial Intelligence: An MIT Perspective%1,
 P. H. Winston and R. H. Brown, editors, 
 MIT Press series in Artificial Intelligence, Cambridge, 1979.

2. Jon Doyle,
 "A Glimpse of Truth Maintenance",
 %2Artificial Intelligence: An MIT Perspective%1,
 P. H. Winston and R. H. Brown, editors, 
 MIT Press series in Artificial Intelligence, Cambridge, 1979.

Internal Reports:

1. Jon Doyle,
 "Analysis by Propagation of Constraints in Elementary Geometry Problem Solving",
 MIT AI Lab WP-108, June 1976.

2. Jon Doyle,
 "The Use of Dependency Relationships in the Control of Reasoning",
 MIT AI Lab WP-133, November 1976.

3. Jon Doyle,
 "Hierarchy in Knowledge Representations",
 MIT AI Lab WP-159, November 1977.

4. Johan de Kleer, Jon Doyle, Charles Rich, Guy L. Steele Jr., and Gerald Jay Sussman,
 "AMORD: A Deductive Procedure System",
 MIT AI Lab Memo 435, January 1978.

Invited Lectures:

1. "What if the Mayans had Escalators",
 Yale University, Computer Science Department, June 23, 1978.

2. "Reflexive Interpreters: A Model for Deliberation, Action, and Introspection",
 University of Pennsylvania, Computer Science Department, October 30, 1979.

3. "Reasoned Deliberation and Decision-Making"
 SRI International, January 14, 1980.

4. "Reasoned Deliberation and Decision-Making"
 Hewlett-Packard, Inc., January 15, 1980.

5. "Reasoned Deliberation and Decision-Making"
 Stanford University, Computer Science Department, January 16, 1980.

6. "Reasoned Deliberation and Decision-Making"
 Xerox Palo Alto Research Center, January 17, 1980.

7. "Reasoned Deliberation and Decision-Making"
 USC Information Sciences Institute, January 24, 1980.

8. "Reasoned Deliberation and Decision-Making"
 Bell Laboratories, February 14, 1980.
.end "multi"

Personal Background and Interests:

.indent 0,0;
Born and raised in Houston, Texas and, in summers, Dundee, Wisconsin, by
Leo M. Doyle and Marilyn C. Doyle.  Unmarried.  Interests in people,
writing, literature, history, economics, musical and poetical composition,
conducting, viola, recorders, painting, sculpture, technology, swimming
and other sports.

.head←77		<< monthly cost of computer account for one person >>
.acad←20;		<< academic pay periods >>
.sum←6;			<< summer pay periods >>
.cand←300*acad+601*sum;	<< candidate salary >>
.srap←279*acad+557*sum; << student salary >>
.inflate←102;		<< inflation rate for salaies 8% for last 4 months >>
.
.tpay←acad + sum;	<< total pay periods >>

.  turn on "%α{→\";
.
.at "$$" incr "."	⊂
.  digc←(incr)[∞-2 to ∞]; digs←(incr)/1000;
.  while("digs>0",|digc←digs[∞-2 to ∞]&","&digc; digs←digs/1000;|);
.("       "[1 to 7-length(digc)]&digc);
.  ⊃
.macro percent(num)	⊂(((num+50)/100)&"α%")⊃;
.
.portion budget; place text
.gtot←0
.macro proj(tit);	⊂ salary←0; tot←0;
.cb "tit";
. ⊃
.macro p(lst,frst,εpay);	⊂
.adjusted←(pay)*inflate/100;
.salary←salary+adjusted;
lst, frst →$$ adjusted.
. ⊃
.recursive macro show(amt,tit);	⊂
.val←amt;
.tot←tot+val;
tit →$$ val.
. ⊃
.<< should be 6.3% travel, 11% other direct >>
.macro fin(num)	⊂
 →----------
   Salary total →$$ salary.
. tot←tot+salary;
. show("(salary*2115+5000)/10000","Staff benefits (21.15α% of salaries)");
. show(salary*42/1000,"Travel");
. if num>0 then start show(head*num*tpay,"Computer cost for num person(s)"); end;;
. show(salary*8/100,"Other direct expenses");
 →----------
   Total direct costs →$$ tot.
. show("(tot*58+50)/100","Indirect costs (58α% of above)");
 →----------
   Project total →$$ tot.
. gtot←gtot+tot;
. ⊃
.
.begin "groups" fill crbreak; preface 0; nojust; indent 0,6;
.proj "Basic AI & Formal Reasoning";
.once fill crspace; indent 0,0;
%2Proposed budget addition to Contract MDA 903-80-C-0102
(DARPA Order No. 2494) for the period 1 October 1980 through 31 October 1981.
.skip;
.cb Professional
.<<
.p(McCarthy,"John (0α% acad., 5α% sum.)","2317*sum/20");
.p(Creary,"Lou (till 1 Sep.'81) ","1063*(tpay-8)");
.p(Goad,"Chris (till 1 Sep.'81)","1054*(tpay-8)");
.p(Ketonen,"Jussi (50α% till 1 Sep.'81)","1250*(tpay-8)/2");
.skip;
.cb Students Research Assistants
.p(Moszkowski,Ben,cand);
.p(------,"",cand);
.p(------,"",cand);
.>>
.p(Doyle,Jon,1054*tpay);
.fin 1;

.if false then start "iu"
.proj(Image Understanding);
%3Professional:%1
.p(Binford,"Thomas (50α%)",1335*tpay/2);
%3Students Research Assistants:%1
.p(Arnold, Reginald,cand);
.p(Brooks, Rod,cand);
.p(Gennery, Donald,cand);
.p(Kim, Scott,cand);
.p(Lowry, Michael,srap);
.fin 13;
.skip;
   Total budget →$$ gtot.
Previous 8 month budget →139,237
   (beginning 1 Jan '80)
.tot←tot+139237;
 →----------
   Two year total →$$ tot.
   Previous two year budget →$$ 412719.
 →----------
.gtot←tot-412719;
   Requested budget increase →$$ gtot.
.end "iu";;
.tty←"total: ">ot;
.end "groups"